#define _CRT_SECURE_NO_WARNINGS 1
#include<string>
#include<iostream>
#include<unordered_map>
using namespace std;

string makeGood(string s) {
    string ret;
    for (const auto& ch : s)
    {
        if (!ret.empty() && tolower(ret.back()) == tolower(ch) && ret.back() != ch) ret.pop_back();
        else ret.push_back(ch);
    }
    return ret;
}

struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int val=0;
};

class Solution {
public:
    unordered_map<int, int> hash;
    int numColor(TreeNode* root) {
        if (root == nullptr) return 0;
        ++hash[root->val];
        numColor(root->left);
        numColor(root->right);
        return hash.size();
    }
};

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); ++i)
    {
        auto it = hash.find(target - nums[i]);
        if (it != hash.end())
            return { it->second,i };
        hash[nums[i]] = i;
    }
    return {};
}


struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* head = nullptr, * tail = nullptr;
    int carry = 0;
    while (l1 || l2 || carry)
    {
        int sum = 0;
        if (l1)
        {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2)
        {
            sum += l2->val;
            l2 = l2->next;
        }
        sum += carry;
        if (!head)
            head = tail = new ListNode(sum % 10);
        else
        {
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }
        carry = sum / 10;
    }
    return head;
}